package OptimalAlgorithm.Linkedlist;


import java.util.List;

//https://leetcode.cn/problems/reorder-list/description/
public class ReorderList {
    public void reorderList(ListNode head) {
        //1、找到链表的中间节点 -> 快慢双指针
        ListNode mid = findMidNode(head);
        //进行链表截断(需要注意)
        ListNode secondHalf = mid.next;
        mid.next = null;
        //2、翻转后半部分链表 -> 头插法
        secondHalf = reverseList(secondHalf);
        //3、合并两个链表 -> （类似合并两个有序链表）双指针
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        ListNode cur1 = head;
        ListNode cur2 = secondHalf;
        while (cur1 != null){
            cur.next = cur1;
            cur1 = cur1.next;
            cur = cur.next;
            if(cur2 != null) {
                cur.next = cur2;
                cur2 = cur2.next;
                cur = cur.next;
            }
        }
        head = newHead.next;
    }
    private ListNode findMidNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    private ListNode reverseList(ListNode mid){
        ListNode newHead = new ListNode();
        ListNode cur = mid;
        while (cur != null){
            mid = mid.next;
            //顺序注意
            cur.next = newHead.next;
            newHead.next = cur;
            cur = mid;
        }
        return newHead.next;
    }

//    public static void main(String[] args) {
//        ListNode head = new ListNode(1);
//        head.next = new ListNode(2);
//        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(4);
//        reorderList(head);
//        System.out.println(head.val);
//        System.out.println(head.next.val);
//        System.out.println(head.next.next.val);
//        System.out.println(head.next.next.next.val);
//    }
}
